package com.springboot.java.design.data_structure;

import java.util.Arrays;

/**
 * @Author: TongRui乀
 * @Date: 2020-09-10 11:14
 * @description：  测试堆
 *
 *      堆使用数组来存放  索引0 空闲 从索引1开始存放数据
 *       i所在的元素表示一个节点且当他是左子树时：
            左子树的索引=2 * i
            右子树的索引=2 * i + 1
            父节点的索引=i / 2
            兄弟节点索引=
 *
 */
public class HeapTest {
    /**
     *  存放数据的数组
     */
    private int[] heap;
    /**
     *  当前元素个数
     */
    private int count;
    /**
     *  堆容量
     */
    private int size;

    HeapTest(int size){
        this.size = size;
        heap = new int[size];
        this.count = 0;
    }

    /**
     *  往堆里添加元素  堆化： 为满足堆的要求 在插入元素后对堆进行调整
     *
     *  插入的元素放入数组尾部  从下向上堆化
     *
     * @param data
     */
    public void add(int data){

        if(count >= size){
            return;
        }

        int i = ++count;
        heap[i] = data;

        heapilyUp(i);
    }

    /**
     *  至下向上堆化
     * @param i
     */
    private void heapilyUp(int i) {
        while (i/2 > 0 && heap[i] > heap[i/2]){
            int temp = heap[i/2];
            heap[i/2] = heap[i];
            heap[i] = temp;
            i = i/2;
        }
    }

    /**
     *  类似上面的方法 但是是从上向下堆化
     * @param data
     */
    public void add2(int data){

        if(count >= size){
            return;
        }

        heap[++count] = data;

        for (int i = 1; i < count; i++) {
            heap(i);
        }


    }

    private void heapilyDown(int i) {
        while (heap[i] < heap[i*2] || heap[i] < heap[i*2+1]){
            int temp = heap[i/2];
            heap[i/2] = heap[i];
            heap[i] = temp;
            i = i/2;
        }
    }


    /**
     *  删除堆顶元素
     *
     *  将数组中的最后一个元素放到数组头部
     */
    public void delete(){

        if(count == 0){
            return;
        }
        // 将数组尾部的元素放到索引1的位置
        int last = heap[count];
        heap[count--] = 0;
        heap[1] = last;

        // 调整以满足堆的要求
        heap(1);
    }

    /**
     *  至上而下堆化
     * @param i
     */
    private void heap(int i){

        int targetIndex = i, index = i;
        // 找到要交换的index
        while (true){

            if(2*i <= count && heap[i] < heap[2*i]){
                targetIndex = 2*i;
                i = 2 *i;
                continue;
            }

            if(2*i+1 <= count &&heap[i] < heap[2*i+1]){
                targetIndex = 2*i+1;
                i = 2*i+1;
                continue;
            }
            break;
        }
        int temp = heap[targetIndex];
        heap[targetIndex] = heap[index];
        heap[index] = temp;
    }

    private static void buildHeap(int[] a, int n) {
        for (int i = n/2; i >= 1; --i) {
            heapify(a, n, i);
        }
    }
    private static void heapify(int[] a, int n, int i) {
        while (true) {
            int maxPos = i;
            if (i*2 <= n && a[i] < a[i*2]) maxPos = i*2;
            if (i*2+1 <= n && a[maxPos] < a[i*2+1]) maxPos = i*2+1;
            if (maxPos == i) break;
            swap(a, i, maxPos);
            i = maxPos;
        }
    }

    private static void swap(int[] a, int i, int maxPos) {

        int temp = a[i];
        a[i] = a[maxPos];
        a[maxPos] = temp;

    }

    /**
     *  堆排序
     *
     *  以大堆顶为例：
     *      根节点一定是最大的元素
     *      将根节点与数组的尾节点交换, 也就是最大的元素放到数组尾部
     *      进行堆化 堆化后的根节点就是第二大元素 然后在交换
     *      后续依次
     */
    public void sort(int i){

        while (i > 1){
            swap(heap, 1, i--);

            for (int j = i; j > 1 ; j--) {
                heapilyUp(j);
            }
        }

    }


    public static void main(String[] args) {

        HeapTest heap = new HeapTest(10);

        heap.add2(1);
        heap.add2(2);
        heap.add2(3);
        heap.add2(4);
        heap.add2(5);
        heap.add2(6);
        heap.add2(7);

        System.out.println(Arrays.toString(heap.heap));

        heap.sort(heap.count);

        System.out.println(Arrays.toString(heap.heap));
    }

}
